package com.ruoyi;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;
/**
 * @Author：chengyu
 * @Package：com.ruoyi
 * @Project：RuoYi-Vue-master
 * @name：SortingAlgorithm
 * @Date：2024/10/27 15:19
 * @Filename：SortingAlgorithm
 */
public class SortingAlgorithm {
    /**
    *@Date：2024/10/27
    *@Author：chengyu
    *@fun：选择排序
    */
//    @Test
    public void testSelectionSort() {
        int[] sorted = {2, 3, 5, 7, 8, 9, 1, 4};
        int[] sortedArray = selectionSort(sorted);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.println(sortedArray[i]);
        }


    }
    public int[] selectionSort(int[] nums) {
        int n = nums.length;
        // 外区间：未排序区间【i, n-1】
        for (int i = 0; i < n - 1; i++) {
            // 内循环：找未排序区间最小元素
            int k = i;
            for (int j = i + 1; j < n; j++) {
                if(nums[j] < nums[k])
                    k = j; // 记录最小元素索引
            }
            // 最小元素与未排序区间的首个元素交换
            int temp = nums[i];
            nums[i] = nums[k];
            nums[k] = temp;
        }
        return nums;
    }
    /**
    * @author:chengyu
    * @date:2024/10/30
    * @fun:冒泡排序
    */
//    @Test
    public void testBubbleSort() {
        int[] sorted = {2, 3, 5, 7, 8, 9, 1, 4};
        int[] sortedArray = bubbleSort(sorted);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.println(sortedArray[i]);
        }
    }
    public int[] bubbleSort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            for(int j = 0; j < i; j++) {
                if(nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums;
    }
    public int[] bubbleSortWithFlag(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            boolean flag = false; // 跳出内循环标志位
            for(int j = 0; j < i; j++) {
                if(nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag)
                break;
        }
        return nums;
    }
    /**
    * @author:chengyu
    * @date:2024/10/31
    * @fun:插入排序
    */
//    @Test
    public void testInsertionSort() {
        int[] sorted = {2, 3, 5, 7, 8, 9, 1, 4};
        int[] sortedArray = insertionSort(sorted);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.println(sortedArray[i]);
        }
    }
    public int[] insertionSort(int[] nums) {
        // 2, 3, 5, 7, 8, 9, 1, 4
        for (int i = 1; i < nums.length; i++) {
            int base = nums[i], j = i - 1;
            while (j >= 0 && nums[j] > base) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = base;
        }
        return nums;
    }
}















